def get_presum(a):
    n=len(a)
    sum=[0]*n
    sum[0]=a[0]
    for i in range(1,n):
        sum[i]=sum[i-1]+a[i]
    return sum

# 求区间a[l]+...+a[r]
def get_sum(sum,l,r):
    if l==0:
        return sum[r]
    else:
        return sum[r]-sum[l-1]

# a=[1,2,3,4,5]
# sum=get_presum(a)
# print("a=",a)
# print("sum=",sum)
# print(get_sum(sum,0,3))